This invention pertains generally to Asynchronous Transfer Mode (ATM) packet switching, and more particularly to methods and systems for switch bandwidth allocation for ATM available bit rate service.
ATM is a networking standard designed to provide simultaneous support for voice, video, and data traffic. An ATM network is packet-switched, but supports only one particular packet sizexe2x80x94a 53-byte packet called a cell. Without regard to the type of information contained in a cell, each ATM cell must have a five-byte cell header and a 48-byte payload.
ATM is connection oriented. That is, two systems must set up an end-to-end xe2x80x9cconnectionxe2x80x9d over the network before they can communicate. But the connection does not require a dedicated circuit like a traditional telephone network connection; instead, the connection is merely a grant of permission to transmit cells at a negotiated data rate, with some guarantees as to quality-of-service (QoS) pararmeters such as minimum cell rate, average cell rate, and network delay. The term commonly used for an ATM connection is a Virtual Channel or xe2x80x9cVCxe2x80x9d.
ATM contains several service classes, each designed to meet the needs of particular types of information sources. The Constant Bit Rate (CBR) service class is most appropriate for sources having a known, constant transmission rate, such as traditional PCM-sampled telephone signals. The Variable Bit Rate (VBR) service class allows some variation in transmission rate but provides bandwidth guarantees, and is appropriate for digital video (e.g., MPEG-coded or H.26x video) and similar applications. The Available Bit Rate (ABR) service class is appropriate for most data transmission. ATM switches monitor their excess capacity (that part not being used by other service classes with guaranteed rates) and allocate that capacity to their ABR connections. Each ABR source is required, in return, to control its rate as directed by the switches in its connection path. Finally, the Unspecified Bit Rate (UBR) service class is also available for data transmission. UBR traffic has no guarantees as to cell loss rate or delay, but places few restraints on the behavior of sources.
ABR and UBR traffic can be regarded as xe2x80x9cbest-effortxe2x80x9d traffic. That is, CBR and VBR traffic have precedence because of their QoS guarantees, and ATM switches work to schedule ABR and UBR traffic around their CBR and VBR. traffic. In order to provide an incentive for best-effort traffic sources to utilize ABR connections, ATM switches attempt to divide their unreserved capacity fairly and efficiently between all competing ABR sources.
The xe2x80x9cERICAxe2x80x9d and xe2x80x9cERICA+xe2x80x9d switch congestion avoidance algorithms, as disclosed by R. Jain et al. in U.S. Pat. No. 5,805,577, represent a state-of-the-art approach to controlling ABR traffic. These algorithms measure switch utilization over xe2x80x9caveraging intervalsxe2x80x9d, including making a count of the number of sources that utilized the switch during the interval. At the end of each such interval, an available ABR capacity for the next such interval is computed. Then, a xe2x80x9cfair sharexe2x80x9d of the available ABR capacity is determined by dividing the capacity by the number of sources that were active over the preceding interval.
An overload factor is also calculated to represent the current overall switch load as a percentage. An explicit rate is then assigned to each source for use during the next measurement interval, based on its current rate, as:
Explicit Rate=max( Fair Share, Current Rate/Overload Factor)
This explicit rate is communicated to its corresponding source.
The present invention is related to ATM switch operation, and more particularly, to allocation of bandwidth between competing ABR sources. The goals of the present invention are to maximize throughput and minimize queueing delay, while treating each source fairly.
The present invention overcomes several shortcomings of prior art algorithms such as xe2x80x9cERICAxe2x80x9d. First, the prior art algorithms do not directly identify, and consider the effect of, sources that cannot or do not wish to transmit their xe2x80x9cfair sharexe2x80x9dxe2x80x94this causes such algorithms to underestimate the true xe2x80x9cfair sharexe2x80x9d available to those sources that want to transmit more, resulting in slow convergence to max-min fairness. Second, these algorithms tend to base each VC""s explicit rate proportionally on that VC""s current rate and on the distance the switch loading is from its optimal loadingxe2x80x94an approach that also slows convergence toward a fair solution. Third, these algorithms generally attempt to distribute one or two global solutions to all sources, instead of predicting individual source behavior and tailoring the solution to each source. Fourth, these algorithms generally cannot provide feedback to sources at a rate that exceeds the switch""s averaging interval. And fifth, these algorithms do not provide for an efficient and fair allocation of bandwidth between ABR and UBR sources.
The present invention includes a recognition of the problems identified above, and solutions to each. For example, one embodiment of the present invention includes a procedure for identifying VC""s that have their rate limited at other points in their connectionxe2x80x94this allows bandwidth that cannot be utilized by such bottlenecked sources to be immediately allocated to other, non-bottlenecked sources. And in one embodiment, overall switch queue congestion is not a direct factor in setting source ratesxe2x80x94instead, the source rate for each source depends on that source""s own current congestion and recent behavior. The present invention also includes embodiments that combine rate measurements, which require an averaging interval, with queue measurements, which do not, in order to provide rate-based feedback that can vary at a rate greater than the averaging interval. And finally, the present invention includes embodiments that allocate some bandwidth explicitly to UBR sources, and yet make excess UBR bandwidth immediately available to ABR sources if UBR sources are under-utilizing it.
In one aspect of the present invention, a method of determining allowable cell rates for sources utilizing a switch is disclosed. The method comprises the steps of estimating the number of rate-controlled sources actively utilizing the switch, and estimating the cell rate available to serve those sources. Active sources that are likely bottlenecked elsewhere in their connection are identified. A reduced available cell rate is estimated by reducing the cell rate available to serve the active sources by a bottlenecked source cell rate based on estimated cell rates of the active sources that are likely bottlenecked elsewhere. Finally, a fair share of the reduced available cell rate is calculated by apportioning the reduced available cell rate among those active sources that are not likely bottlenecked elsewhere.
In a second aspect of the invention, a method of providing rate feedback to a rate-controlled source utilizing a switch is disclosed. The switch monitors the cell queue occupancy for the rate-controlled source. Upon receiving a backward resource management cell bound for the rate-controlled source, the switch calculates an explicit rate for the source based on a fair share rate and the source""s predicted cell queue occupancy. The switch then inserts the explicit rate in the backward resource management cell when the explicit rate is lower than the explicit rate already contained in the cell.
In yet another aspect of the invention, a cell switch is disclosed. The cell switch comprises a cell queue that maintains a source cell queue for each rate-controlled source utilizing the switch, and a cell counter that counts the number of cells passing through each source cell queue. The cell switch further comprises a bottlenecked source detector that detects bottlenecked sources based on statistics calculated by the cell counter. Preferably, the cell switch also has a resource management cell processor that calculates an explicit rate for a resource management cell passing through the switch, based on a rate supplied by an available bit rate estimator, cell rate statistics calculated by the cell counter for the source corresponding to the resource management cell, and source queue occupancy statistics calculated by the cell queue for the source corresponding to the resource management cell.